package pack2;

import java.util.Arrays;

public class quickSort {

    public static void main(String[] args) {
        int[]array={99,4,5,6,1,3,2,8,5,4,1,3,1,8,4,7,1,9};
        int[]bad={99,88,55,22,11,8,7,4,3,2,1};
        int[]easy={3,1,2,1};
        int[]arr=quickSort(array);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 这个方法是为了统一接口写的。
     * @param array 待排序数组
     * @return
     */
    public static int[]quickSort(int[]array){
        int low=0;
        int high= array.length-1;
        quick(array,low,high);
        return array;
    }

    /**
     * 快速排序
     * 快速排序最核心的思路就是找到基准值，然后通过基准值将数组划分为左部分和右部分，然后通过递归对
     * 数组进行排序
     * @param array
     * @param low
     * @param high
     */
    public static void quick(int[]array,int low,int high){
        if(high<=low){return;}
        int index=pqrtitionHole(array,low,high);
        quick(array,low,index-1);
        quick(array,index+1,high);

    }
    /**找基准下标：Hoare法
     * 基本思路为将数组0下标作为key值，记录下当前区间最左边小标和值，定义low和high分别为(0,array.length),为从最右边high
     * 先依次向左找到，小于key的元素下标，记录下新的high下标，再从low依次向右找到大于key的元素下标，记录下新的low下标，将low,和high下标值数组值
     * 进行交换，重复上述操作，直到low==high,最后再将最左下标值与基准下标值交换即可
     * @param array 待排序数组
     * @param low 当前待排序数组(数组的左部分或右部分)最左下标
     * @param high 当前待排序数组(数组的左部分或右部分)最右下标
     */
    public static int partitionHoare(int[]array,int low,int high){
        //分别记录下当前区间最左边小标和值。
        int key=low;
        int temp=array[low];
        while(low<high){
            //以最左边为key值，先找到右边比key值小的数的下标。
            while(low<high&&array[high]>=array[key]){
                    high--;
            }
            while(low<high&&array[low]<=array[key]){
                    low++;
            }
            swap(array,low,high);
        }
        //当low下标high下标相等时，交换key值与此时的基准下标值(low或者high都可)。
        swap(array,key,low);
        //返回基准下标值
        return low;
    }

    /**找基准下标：挖坑法
     * 大致思路为，基本思路为将数组0下标作为key值，将key值储存在一个临时变量temp内(形成一个坑)，为从最右边high，先依次向左找到
     * 小于temp的元素下标，记录下新的high下标，然后将high下标元素的值赋值给low下标的元素(将high下标的值去填坑，此时high下标形成一个新的坑)，
     * 此时，再从low依次向右找到大于temp的元素下标，记录下新的low下标，将low下标元素的值赋值给high下标的元素(将high下标的值去填坑，此时low下
     * 标形成一个新的坑)，重复以上操作，直到low==high.
     * @param array
     * @param low
     * @param high
     * @return
     */
    public static int pqrtitionHole(int[]array,int low,int high){
        int temp=array[low];
        while(low<high){
            while(low<high&&array[high]>=temp){
                high--;
            }
            array[low]=array[high];
            while(low<high&&array[low]<=temp){
                low++;
            }
            array[high]=array[low];
        }
        array[low]=temp;
        return low;
    }



    /**
     * 交换数组中两个下标元素值
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[]array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
}
